﻿// 104 排序5.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <memory.h>
using namespace std;
/*
http://oj.daimayuan.top/course/22/problem/937

给定 n个正整数 a1,a2,…,an，请将它们从小到大排序，然后输出。
并且输出原来每个数字排完序后在第几位（对于相同的数字，序号小的排在前面）。

输入格式
第一行一个整数 n，表示数字个数。

接下来一行包含 n 个整数 a1,a2,...,an。

输出格式
第一行 n个整数，表示排完序之后的结果。

第二行 n个整数，表示原来每个数字排完序后在第几位。

样例输入
5
3 9 5 3 2
样例输出
2 3 3 5 9
2 5 4 3 1
数据规模
对于 100%的数据，保证 1≤n≤105,1≤ai≤105。
*/

int n, m = 100000, a[100001], r[100001], c[100001];

void countingsort() {
	memset(c, 0, sizeof c);
	for (int i = 1; i <= n; i++)
		++c[a[i]];
	for (int i = 1; i <= m; i++)
		for (int j = 1; j <= c[i]; j++)
			printf("%d ", i);
	printf("\n");
	for (int i = 2; i <= m; i++)
		c[i] += c[i - 1];
	for (int i = n; i; --i)
		r[i] = c[a[i]]--;
	for (int i = 1; i <= n; i++)
		printf("%d ",r[i]);
	printf("\n");
}

int main()
{
	scanf("%d",&n);
	for (int i = 1; i <= n; i++)
		scanf("%d",&a[i]);
	countingsort();

	return 0;
}

 